package m202406.d23;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/23 22:04
 */
public class Q312 {
    public int maxCoins(int[] nums) {
        int[][] dp = new int[nums.length + 2][nums.length + 2];
        int[] v = new int[nums.length + 2];
        v[0] = 1;
        v[nums.length + 1] = 1;
        for (int i = 0; i < nums.length; i++) {
            v[i + 1] = nums[i];
        }

        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 2; j < dp[0].length; j++) {
                int max = 0;
                for (int k = i + 1; k < j; k++) {
                    max = Math.max(max, v[k] * v[i] * v[j] + dp[i][k] + dp[k][j]);
                }
                dp[i][j] = max;
            }
        }
        return dp[0][nums.length + 1];
    }
}
